package com.data_structure_algorithm.sort;

import java.util.Arrays;

public class CharuSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 7, 8, 63, 21, 5, 7, 8};
        sort(arr);

        System.out.println(Arrays.toString(arr));

        /*int[] arrs = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arrs[i] = (int) (Math.random() * 80000000);
        }
        String dateStart = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());
        System.out.println(dateStart);
        sort(arrs);
        String dateEnd = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());

        System.out.println(dateEnd);*/
    }


    public static void sort(int[] arr) {

        //首元素为有序表   {  1, 3,7, 8,  63,      21, 5, 7, 8};
        //首次索引为1和首元素比较
        for (int i = 0; i < arr.length - 1; i++) {
            int insertVal = arr[i + 1];//待插入数据，即无序列表首元素

            int insertIndex = i;//有序列表末尾元素下标
            //下标位越界并且后面比前面小，说明待插入位置还未找到合适位置，还需要继续往前找
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                //有序列表末尾元素后移
                arr[insertIndex + 1] = arr[insertIndex];
                //继续向前找  如果一直不满足，就一直往前插，直到找到合适位置
                insertIndex--;
            }
            //推出循环说明找到合适位置  insertVal（待插入数据） >= arr[insertIndex]
            //故arr[insertIndex ++]的位置是insertVal的位置
            //即使当前插入的值和arr[insertIndex]的值相等，arr[insertIndex+1]才是最终位置，因为插排是稳定的
            //-----
            //如果首次比较就到了这里，说明待插入数据正好比有序列表末尾数据大，那么待插入数据就成为了有序列表的最后端
            //即 arr[insertIndex + 1]
                //如果有序列表的末尾索引下标是i,说明i所在位置正好是待插入位置，
                // 符合本轮循环初始化的待插入值和有序列表末尾索引的值，无需赋值
                arr[insertIndex + 1] = insertVal;
        }

    }
}
